#include <sys/time.h>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
using namespace std;
const int N = 100;
float m[N][N];
void m_reset()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i; j++)
			m[i][j] = 0;
		m[i][i] = 1.0;
		for (int j = i + 1; j < N; j++)
			m[i][j] = rand();
	}
	for (int k = 0; k < N; k++)
		for (int i = k + 1; i < N; i++)
			for (int j = 0; j < N; j++)
				m[i][j] += m[k][j];
}
int main() {
	struct timeval start;
	struct timeval end;//clock
	float timecount=0;
	int comm_sz;
	int my_rank;

	MPI_Init(NULL, NULL);
	MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

	int r1 = my_rank * (N - N % comm_sz) / comm_sz;
	int r2;
	if (my_rank != comm_sz - 1)
		r2 = my_rank * (N - N % comm_sz) / comm_sz + (N - N % comm_sz) / comm_sz - 1;
	else r2 = N - 1;

	if (my_rank == 0) {
		m_reset();
		for (int i = 1; i < comm_sz; i++)
			MPI_Send(m, N * N, MPI_FLOAT, i, 0, MPI_COMM_WORLD);
	}
	else MPI_Recv(m, N * N, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);//init m[][] and send to all
	gettimeofday(&start, NULL);
	
	for (int k = 0; k < N; k++)
	{
		if (r1 <= k && k <= r2)
		{
			for (int j = k + 1; j < N; j++)
				m[k][j] = m[k][j] / m[k][k];
			m[k][k] = 1.0;
			for (int num = my_rank; num < comm_sz; num++)
				MPI_Send(&m[k][0], N, MPI_FLOAT, num, 1, MPI_COMM_WORLD);
		}
		else {
			if (k <= r2)
				MPI_Recv(&m[k][0], N, MPI_FLOAT, (int)(k / ((N - N % comm_sz) / comm_sz)), 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
			else break;
		}
	}

	MPI_Finalize();
	gettimeofday(&end, NULL);
	timecount += (end.tv_sec - start.tv_sec) * 1000000 + end.tv_usec - start.tv_usec;
	cout << timecount << endl;
	return 0;
}